Теорема о полноте полиномов Жегалкина

Любая булева функция задается полиномом Жегалкина, и притом единственным.

**Существование** следует из полноты системы $\{+, \cdot, 1\}$ и эквивалентности формул над этой системой полиномам Жегалкина. **Единственность**: Зафиксируем алфавит переменных $\Sigma = \{x_{1}, \dots, x_{k}\}$. Над ним существует $2^{2^{k}}$ различных булевых функций. Количество различных одночленов над $\Sigma$ равно $2^{k}$ (биекция с подмножествами переменных). Полиномы Жегалкина биективно отображаются на множества одночленов, следовательно, всего существует $2^{2^{k}}$ различных полиномов. Отображение, ставящее в соответствие полиному задаваемую им функцию, является сюръекцией (из доказанного существования). Так как мощности множеств полиномов и функций совпадают и конечны, эта сюръекция является биекцией (инъекцией). $\square$